package demo.practice.trie;

import java.util.HashMap;
import java.util.Map;

public class MagicDictionary {
    //p676


    public static void main(String[] args) {
        MagicDictionary magicDictionary = new MagicDictionary();
        magicDictionary.buildDict(new String[]{"a","b","ab","abc","abcabacbababdbadbfaejfoiawfjaojfaojefaowjfoawjfoawj","abcdefghijawefe","aefawoifjowajfowafjeoawjfaow","cba","cas","aaewfawi","babcda","bcd","awefj"});
        boolean hello = magicDictionary.search("abcd");

        System.out.println(hello);
    }

    Map<Character, MagicDictionary> child = new HashMap<>();
    boolean isend = false;

    public MagicDictionary() {

    }

    public void buildDict(String[] dictionary) {


        for (String s : dictionary) {
            MagicDictionary cur = this;
            for (char c : s.toCharArray()) {
                if (cur.child.get(c) == null) {
                    //cur=cur.child.get(c);//匹配到了直接跳
                    cur.child.put(c, new MagicDictionary());
                }
                cur = cur.child.get(c);
            }
            cur.isend = true;//单词结尾了
        }
    }

    public boolean search(String searchWord) {

        for (int i = 0; i < searchWord.length(); i++) {
            MagicDictionary cur = this;

            int j = 0;
            while (j < i) {
                char c = searchWord.charAt(j);
                if (cur.child.get(c) != null) {
                    cur = cur.child.get(c);
                } else {
                    break;
                }
                j++;
            }

            if(j!=i){
                continue;
            }

            if(i==searchWord.length()-1 ){//只要有 不和最后一位相同的char 就可以替换
                for (Map.Entry<Character, MagicDictionary> chd : cur.child.entrySet()) {
                    if (chd.getKey() != searchWord.charAt(i)&& chd.getValue().isend)
                        return true;
                }
            }else {
                boolean res = false;
                for (Map.Entry<Character, MagicDictionary> chd : cur.child.entrySet()) {
                    if (chd.getKey() != searchWord.charAt(i))
                        res = res || childSeach(searchWord, i + 1, chd.getValue());
                }
                if (res)
                    return true;
            }
        }

        return false;
    }

    private boolean childSeach(String searchWord, int i, MagicDictionary cur) {
        for (; i < searchWord.length(); i++) {

            char c = searchWord.charAt(i);
            if (cur.child.get(c) != null) {
                cur = cur.child.get(c);
            } else {
                return false;
            }
        }
        return cur.isend;
    }
}
